﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;


namespace ShapeConnectors
{
    class Prim:CANHNA 
    {
        // stepprim lưu lại danh sách các bước của thuật toán
        public static List<BuocThucHien> StepPrim;

        List<CANHNA> T = new List<CANHNA>();
        private int nT;
        List<int> nhanprim = new List<int>();
        List<int> labelprim = new List<int>();
        string chuoi = null;
        public string XuatPrim()
        {
            int kq = KTLT();
            PrimAlg();
            int temp = 0;
            if (kq == 1)
            {
                chuoi = "Cây tối đại ngắn nhất: ";
                for (int i = 0; i < nT; i++)
                {
                    temp += T[i].GetTS();
                    chuoi += T[i].GetDinh1().ToString() + "->" + T[i].GetDinh2().ToString() + "\r\n";
                }
                chuoi = chuoi + "\r\n Trọng số :" + temp.ToString();
            }
            else
                chuoi = "Đồ thị không liên thông";
            return chuoi;
        }
        public void ViSit(int i, int lb)
        {
            labelprim[i] = lb;
            for (int j = 0; j <spt; j++)
            {
                if (labelprim[j] == 0 && (a[i, j] > 0))
                {
                    ViSit(j, lb);
                }
            }
        }
        public int KTLT()
        {
            int lb = 0;
            for (int i = 0; i < spt; i++)
                labelprim.Add(0);
            for (int i = 0; i < spt; i++)
            {
                if (labelprim[i] == 0)
                {
                    lb++;
                    ViSit(i, lb);
                }
            }
            if (lb ==1)
                return 1;
            return 0;
        }
        public void PrimAlg()
        {
            StepPrim = new List<BuocThucHien>();
            nT = 0;
            for (int i = 0; i < spt; i++)
                nhanprim.Add(0);
            nhanprim[0] = 1;
            while (nT < spt - 1)
            {
                //"buoc " lưu từng bước của thuật toán
                BuocThucHien buoc = new BuocThucHien();//
                buoc.KhoiTao();//khởi tạo các đối tượng của 1 bước//
                CANHNA emin=new CANHNA();
                int nmin=-1;
                for (int w = 0; w < spt; w++)
                {
                    if (nhanprim[w] == 0)
                    {
                        for (int v = 0; v < spt; v++)
                        {

                            if (nhanprim[v] == 1 && a[w, v] != 0)
                            {
                                CANHNA temp=new CANHNA();//
                                temp.SetDinh1(v);//
                                temp.SetDinh2(w);//
                                temp.SetTS(a[w,v]);//
                                buoc.Canhlienquan.Add(temp);//
                                if (nmin == -1 || a[w, v] < nmin)
                                {
                                    nmin = a[w, v];
                                    emin.SetDinh2(w);
                                    emin.SetDinh1(v);
                                    emin.SetTS(nmin);
                                }
                                
                            }
                        }
                    }
                }
                T.Add(emin);
                for (int i = 0; i < T.Count; i++)
                    buoc.KetQuaPrim.Add(T[i]);
                buoc.Canhcanto = emin;//
                buoc.Dinhcanto = emin.GetDinh2();//
                nT++;
                nhanprim[emin.GetDinh2()] = 1;
                StepPrim.Add(buoc);//
            }
        }  
    }
}
